In the present state of high speed, electronic communications, there are a variety of problems which require the power and flexibility of loadable, finite state automata as well as a fast interpreter cycle. There presently exists a broad class of fast and flexible electronic devices which must communicate with each other. The National Bureau of Standards (NBS) has established standards for the interface between the channels of main frame computers and the controllers of disk and tape devices. This has been published in three different publications entitled: I/O Channel Interface Standard (FIPS PUB 60); Operational Specifications for Magnetic Tape Subsystems (FIPS PUB 62); and Operational Specifications for Rotating Mass Storage Subsystems (FIPS PUB 63). These publications are available from the National Technical Information Service, Springfield, Va., and were published in 1979. However, there is the need for a passive monitor for the parallel bus used for this interface.
Standard logic analyzers provide various complex triggering schemes (such as disclosed in K101D/K102D Logic Analyzer Operations Manual by Gould, Inc. of Santa Clara, Calif. (1983)), and fast data capture before and after the trigger. But the trigger normally is an instantaneous pattern in the data being monitored, and there exists a limited capability for detecting sequences of patterns.
It is easy to build fast, static finite state automata to monitor interfaced bus interactions using standard electrical circuit components. In fact, a finite state automaton (FSA) model has been proposed which monitors the interactions on the bus, identifies key interactions, and selects appropriate actions at the key points. This FSA model is often used in the design of circuits. The resulting circuit, or FSA, is permanently defined, however, and changes to the state diagram may lead to major circuit changes.
It is also easy to build a slow, loadable FSA interpreter, using a microcomputer and software. Algorithms with various optimizations are widely known (See e.g., A. V. Aho and J. D. Ullman, "The Theory of Parsing, Translation, and Compiling" Vol. 1: Parsing (Prentice-Hall 1972) and A. V. Aho and J. D. Ullman, "Principles of Compiler Design" (Addison Wesley 1977)). There are probably literally thousands of programs using these techniques. For example, many compilers use an FSA for scanning and classifying an input as identifiers, numeric literals, special characters, etc. (See e.g., P. M. Lewis II, D. J. Rosenkrantz and R. E. Stearns, "Compiler Design Theory," (Addison Wesley 1976)). One standard software technique uses a table stored in memory to define an FSA, and an algorithm used to interpret this table. This interpreter, however, is implemented in software and is thus quite slow and usually requires a large amount of memory space.
It has also been proposed to use a partitioned finite state automaton as a hardware pattern matcher for large text retrieval systems (R. L. Haskins and L. A. Hollaar, "Operational Characteristics of a Hardware-Based Patterned Matcher, ACM Transactions on Database Systems," 1983). This hardware pattern matcher requires analysis of an FSA definition to construct loadable tables. It uses a rather unique method to achieve a fast, loadable FSA interpreter using reasonable memory requirements.
The finite state class of automata can be described in various ways for different purposes. However, for the present purpose, an FSA is comprised of:
a set of states; PA1 a designation of an initial state; PA1 a set of input characters; PA1 a set of transitions from each state to the same or other states with a separate transition for each combination of state and input character; and PA1 an action associated with each transition which may produce external results, but does not affect the state.
Most FSA definitions also include a set of final states.
The straightforward implementation of FSA in software is a large rectangular table with a row for each state and a column for each input character. Each entry in the table contains a new state and an action. An interpreter uses a single table lookup for each cycle, and the result can be a table having an enormous size even for simple FSA definitions.
Most FSA's that arise in practice are sparse. Within a given state, only a few of the many possible input characters cause distinctive transitions. The transitions for all other input characters (for that state) are identical and may be lumped together as the default transition. Usually, the default transition for another state will be different.
Various optimizations of the straightforward implementation make use of such sparseness to reduce the size of the table by storing one default transition for each state and all the other non-default or regular transitions. The regular transitions can be stored in a linked list for each state. Alternatively, the state and input character can be hashed to index a scatter table of transitions with some method for resolving collisions. Such methods often require several table lookups to complete a single transition and a number of extra cycles is unbounded for some methods.
There therefore exists the need for a finite state automaton interpreter which can be loaded with the criteria for various FSA's so that a broad class of problems can be solved. Such an interpreter is particularly needed where higher speed is required than that available from a programmed, general-purpose digital computer.